package everydayone.diameteroftree;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/10
 * @author 王光浩
 * @Thinking 使用递归+中序遍历完成。要解决该题我们需要明白最长直径只会来源于某一个子树，且该子树的左子数
 * 			  的最长直径+右子树的最长直径+2等于最长直径。
 * @Analysis 时间复杂度O（n），空间复杂度O（1）——不考虑栈的使用。
 */
public class MyMethodOne {
	private int maxLength=0;
    public int diameterOfBinaryTree(TreeNode root) {
    	recursively(root);
    	return this.maxLength;
    }
    /**
     * 进行中序遍历，每次将root子树的最长左子树直径+最长右子树直接+2与maxLength比较大小
     * @param root
     * @return 左右子树中最长直径+1
     */
    private int recursively(TreeNode root) {
    	if(root==null)return -1;  //抵消当左右子树为null时，left=1，right=1的情况
    	int left=recursively(root.left)+1;
    	int right=recursively(root.right)+1;
    	this.maxLength=((left+right)>this.maxLength)?(right+left):this.maxLength;
    	return left>right?left:right;
    }
}
